package main

import "fmt"

func main() {
	heights := []int{2,1,5,6,2,3}
	fmt.Println(largestRectAngleArea(heights))
}

/**
思路：
1. 固定一个矩形的高度，找到该矩形的最大宽度，则该矩形所能形成的最大面积为 高度 * 宽度
2. 栈中保存的是数组索引下标
3. 该矩形的最大宽度即为 右边第一个比该矩形低，左边第一个比该矩形低，这左右两边矩形的宽度即为该矩形的最大宽度
4. 因为是单调递增栈(可以相等)，所以栈顶的前一个元素就是要找的左边第一个矩形，当栈只有一个元素时，栈顶的前一个元素为 -1
5. 遍历完数组后，遍历栈来统计为处理的元素
6. 更具体看官网解析说明
 */
func largestRectAngleArea(heights []int) int {
	stack := make([]int, 0, len(heights))
	max := 0

	for idx := range heights{
		for  len(stack) > 0 && heights[stack[len(stack) - 1]] > heights[idx] {
			prev := 0
			if len(stack) > 1 {
				prev = stack[len(stack) - 2]
			}else {
				prev = -1
			}

			maxW := idx - prev - 1
			maxArea := maxW * heights[stack[len(stack) - 1]]
			if max < maxArea {
				max = maxArea
			}

			stack = stack[:len(stack) - 1]
		}

		stack = append(stack, idx)
	}

	// 统计栈中未处理的元素
	prev := -1
	for _, val := range stack{
		maxW := stack[len(stack) - 1]  - prev
		maxArea := heights[val] * maxW
		if max < maxArea {
			max = maxArea
		}

		prev = val
	}

	return max
}
